A number of Wi-Fi-based indoor positioning systems exist in the prior art. These systems are usually classified into three categories: propagation-based systems; signal strength map-based systems; and hybrid systems. For more information, see F. Lassabe, Geolocalisation et prediction dans les reseaux Wi-Fi en interieur, Phd thesis, LIFC, University of Franche-Comte, France, Apr. 21, 2009.
There are two types of signal strength map-based positioning systems: deterministic systems and probabilistic systems. The deterministic system approach relies on an average signal strength map database. To locate a mobile device (M), database content and real-time measurements are compared. Positioning systems in this family require physical coordinates and average signal strength (SS) values. For every physical coordinate in such a system, SS measurements of transmissions by a mobile device at the given physical location are taken at every system waypoint (YP). Typically, not all YPs will detect the transmitted signal, and at those YPs, the recorded SS will be zero.
A location record has the following form: (p, ss1, . . . , ssN) where p are coordinates and (ss1, . . . , ssN) are signal strength measurements. The database may include additional application-specific data (in separate records), such as signal quality (data rate, errors, etc.). For example, in RADAR systems, mobile orientation is stored along with coordinates and signal strength measurements. For more information, see Paramvir Bahl and Venkata N. Padmanabhan, “RADAR: An in-building RF-based user location and tracking system”, In INFOCOM (2), 2000, pages 775-784.
Some systems disambiguate between points based on past locations. They use a Viterbi-like algorithm to give greater weight to points closer to the last known location. They also account for factors that affect signal strength in known ways by using signal strength measurement profiles based on a variety of criteria. For example, signal strength measurements vary based on crowd density, which can often be predicted based on the time of day.
Using the closest point in signal strength space without further refinement is one proposed algorithm. In an improvement to that system, several points in the database are selected (the closest ones from the measurement transmitted) and the weighted average location is computed as follows:
  p  =                    ∑                  j          =          1                k            ⁢                        1                                    d              ⁡                              (                                                      s                    ⁢                                                                                  ⁢                                          s                      ij                                                        ;                                      s                    ⁢                                                                                  ⁢                    s                                                  )                                      +            ɛ                          ⁢                  p          ij                                    ∑                  j          =          1                k            ⁢              1                              d            ⁡                          (                                                s                  ⁢                                                                          ⁢                                      s                    ij                                                  ;                                  s                  ⁢                                                                          ⁢                  s                                            )                                +          ɛ                    where d(ssij; ss) is signal strength space Euclidean distance between database measurements ss1 and current measurement ss and ε is a very small constant used to avoid divide by zero errors.
Probabilistic systems are based on signal strength measurement sets for each location in the signal strength database. Using large data sets can lead to high computational loads. Solutions have been proposed to address this problem. Two algorithms are exposed—joint clustering and incremental triangulation—to cluster data and reduce the search space (lessen the number of records to evaluate) used to locate a mobile device, which reduces the computational time. Other systems use Bayesian inference to locate mobile devices in rooms and based on signal strength discretized histograms.
Thus, there are a number of algorithms in the literature that estimate a device's position based on information from radio signal strength maps. (Such algorithms are known as signal strength cartography or RF signature). The signal strength measurements required to compute the RF signature can be obtained from either the mobile device to be located or from the infrastructure around mobile device. Both approaches have their shortcomings.
Measuring signal strength on the mobile device requires low level access to the wireless hardware. But mobile device software applications frequently are denied such access. Moreover, relying on mobile devices themselves to provide their signal strength measurements raises some problems about hardware and software heterogeneity, which is why existing solutions that implement this approach require custom hardware (asset tracking tags).
In order to obtain signal strength information from the 802.11 infrastructure, the APs within range of the mobile devices requires customizing the APs in a way that commercial infrastructure providers do not allow. Existing solutions that implement this approach can be developed only by 802.11 vendors, and all such solutions work exclusively on the infrastructure provided by the vendor.